additive Additive may refer to: Mathematics * Additive function, a function in number theory * Additive map, a function that preserves the addition operation * Additive set-functionn see Sigma additivity * Additive category, a preadditive category with f ...

and

algebraic number theory Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...

, the Skolem–Mahler–Lech theorem states that if a sequence of numbers satisfies a

linear difference equation Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...

, then with finitely many exceptions the positions at which the sequence is zero form a regularly repeating pattern. This result is named after

Thoralf Skolem Thoralf Albert Skolem (; 23 May 1887 – 23 March 1963) was a Norwegian mathematician who worked in mathematical logic and set theory. Life Although Skolem's father was a primary school teacher, most of his extended family were farmers. Skolem ...

(who proved the theorem for sequences of

rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...

s),

Kurt Mahler Kurt Mahler FRS (26 July 1903, Krefeld, Germany – 25 February 1988, Canberra, Australia) was a German mathematician who worked in the fields of transcendental number theory, diophantine approximation, ''p''-adic analysis, and the geometry of ...

(who proved it for sequences of

algebraic number An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...

s), and

Christer Lech Christer or Krister are varieties of the masculine given name Kristian, derived from the Latin name ''Christianus'', which in turn comes from the Greek word ''khristianós'', which means "follower of Christ". The name, written in its two variants C ...

(who proved it for sequences whose elements belong to any

field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...

of characteristic 0). Its known proofs use

p-adic analysis In mathematics, ''p''-adic analysis is a branch of number theory that deals with the mathematical analysis of functions of ''p''-adic numbers. The theory of complex-valued numerical functions on the ''p''-adic numbers is part of the theory of lo ...

and are

non-constructive In mathematics, a constructive proof is a method of mathematical proof, proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also ...

Theorem statement

Let

s(n)_

be a sequence of

complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...

s satisfying

s(n) = c_1 s(n-1) + c_2 s(n-2) + \cdots + c_d s(n-d)

for all

n \ge d

, where

c_i

are complex number constants (i.e., a

constant-recursive sequence In mathematics and theoretical computer science, a constant-recursive sequence is an infinite sequence of numbers where each number in the sequence is equal to a fixed linear combination of one or more of its immediate predecessors. A constan ...

of order

d

). Then the set of zeros

\

is equal to the

union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...

of a

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...

and finitely many

arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...

s. If we have

c_d \ne 0

(excluding sequences such as 1, 0, 0, 0, ...), then the set of zeros in fact equal to the union of a finite set and finitely many ''full'' arithmetic progressions, where an infinite arithmetic progression is full if there exist integers ''a'' and ''b'' such that the progression consists of all positive integers equal to ''b'' modulo ''a''.

Example

Consider the sequence :0, 0, 1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, ... that alternates between zeros and the

Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...

s. This sequence can be generated by the linear recurrence relation :

F(i) = F(i-2) + F(i-4)

(a modified form of the Fibonacci recurrence), starting from the base cases ''F''(1) = ''F''(2) = ''F''(4) = 0 and ''F''(3) = 1. For this sequence, ''F''(''i'') = 0 if and only if ''i'' is either one or even. Thus, the positions at which the sequence is zero can be partitioned into a finite set (the

singleton set In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the ...

) and a full arithmetic progression (the positive

even number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because \begin -2 \cdot 2 &= -4 \\ 0 \cdot 2 &= 0 \\ 41 ...

s). In this example, only one arithmetic progression was needed, but other recurrence sequences may have zeros at positions forming multiple arithmetic progressions.

Related results

The

Skolem problem In mathematics, the Skolem problem is the problem of determining whether the values of a constant-recursive sequence include the number zero. The problem can be formulated for recurrences over different types of numbers, including integers, ratio ...

is the problem of determining whether a given recurrence sequence has a zero. There exist an algorithm to test whether there are infinitely many zeros, and if so to find the decomposition of these zeros into periodic sets guaranteed to exist by the Skolem–Mahler–Lech theorem. However, it is unknown whether there exists an algorithm to determine whether a recurrence sequence has any non-periodic zeros .

References

* , cited in Lech 1953. * , cited in Lech 1953. * . * . * . *.

External links

* {{DEFAULTSORT:Skolem-Mahler-Lech theorem Theorems in number theory Algebraic number theory Additive number theory Recurrence relations